// 给定一个整数数组nums和一个整数k，找出nums中和至少为k的最短非空子数组，并返回该子数组的长度，如果不存在这样的子数组，返回-1
// 思路，构造前缀和，维护单调队列，更新和大于等于k的最短数组长度

function shortestSubarray(nums, k) {
    let sum = [0]
    for (let i = 0; i < nums.length; i++) {
        sum[i+1] = sum[i] + nums[i]
    }
    let queue = [0] // 前缀和递增队列，存的元素是索引位置
    let ans = Infinity
    for (let i = 0; i < sum.length; i++) {
        let pos = -1
        while (queue.length && (sum[i] - sum[queue[0]] >= k)) {
            pos = queue.shift()
        }
        if (pos !== -1) {
            ans = Math.min(i - pos, ans)
        }
        // 维持单调递增队列，因为如果j > i,s[j]小于s[i]，那么去掉i，因为j的值更小，位置更靠后，更小的值，更大的索引位置
        while (queue.length && sum[queue[queue.length - 1]] > sum[i]) {
            queue.pop()
        }
        queue.push(i)
    }
    return ans === Infinity ? -1 : ans
}

let nums = [2, -1, 2], k = 3
console.log(shortestSubarray(nums, k));